package com.emeraldparser.grammar;

import static com.emeraldparser.symbol.SymbolClasses.concat;

import java.util.Collection;
import java.util.Deque;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.emeraldparser.parse.ClassWriter;
import com.emeraldparser.parse.ParseState;
import com.emeraldparser.symbol.CharSequenceSymbolClass;
import com.emeraldparser.symbol.CharacterRangeSymbolClass;
import com.emeraldparser.symbol.CharacterSymbolClass;
import com.emeraldparser.symbol.SymbolClass;
import com.emeraldparser.symbol.SymbolClass.State;
import com.emeraldparser.symbol.SymbolClasses;
import com.emeraldparser.util.Automaton;
import com.emeraldparser.util.Automatons;
import com.emeraldparser.util.GraphAutomaton;
import com.emeraldparser.util.HashBasedMultitable;
import com.emeraldparser.util.HashCodes;
import com.emeraldparser.util.Multitable;
import com.emeraldparser.util.Pair;
import com.emeraldparser.util.Path;
import com.google.common.base.Predicates;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;

public class GrammarTest {

	private static final int MAX_LOOKAHEAD_SIZE = 0;
	private Grammar grammar;
	private Set<Rule> rules = Sets.newHashSet();
	private Automaton<SymbolClass.State, SymbolClass> automaton;
	private Collection<SymbolClass.State> leftStates = Sets.newHashSet();
	private Collection<SymbolClass.State> rightStates = Sets.newHashSet();
	private Map<SymbolClass.State, Rule> rulesByState = Maps.newHashMap();
	private Multitable<ParseState, SymbolClass, Action> actionTable = HashBasedMultitable.create();
	private Automaton<ParseState, SymbolClass> parseAutomaton;
	private Map<ParseState, Automaton<?, ?>> lookAheadAutomatonsByState = Maps.newHashMap();
	private Set<Rule> nullableRules = Sets.newHashSet();
	private Map<SymbolClass.State, SymbolClass> symbolClassesByState = Maps.newHashMap();

	public static void main(String... args) throws Exception {
		new GrammarTest(Grammars.buildGrammarGrammar()).run();
		
		/*
		Table<String, String, String> table = HashBasedTable.create();
		table.put("A", "B", "C");
		table.put("A", "C", "D");
		table.put("G", "T", "E");
		
		System.out.println(table);
		
		Multimap<String, String> mm = HashMultimap.create();
		mm.put("A", "B");
		mm.put("A", "C");
		mm.put("B", "C");
		System.out.println(mm);
		*/
	}

	public GrammarTest(Grammar grammar) {
		this.grammar = grammar;
	}

	public void run() throws Exception {
		rules.addAll(grammar.getRules());
		
		automaton = GraphAutomaton.create();
		
		Grammar.Builder newGrammarBuilder = Grammar.builder().addAll(grammar);
		
		boolean modified;
		do {
			modified = false;
			

			for (Rule rule : rules) {
				Automaton<SymbolClass.State, SymbolClass> leftAutomaton = rule.getLeftAutomaton();
				Automaton<SymbolClass.State, SymbolClass> rightAutomaton = rule.getRightAutomaton();
				
				if (rule.toString().contains("rule =")) {
					System.out.print("");
				}
				
				System.out.println(rule + ":");
				
				System.out.println("  " + leftAutomaton);
				System.out.println("  =");
				System.out.println("  " + rightAutomaton);
				System.out.println();
				
				automaton.addAll(leftAutomaton);
				automaton.addAll(rightAutomaton);
				
				leftStates.addAll(leftAutomaton.vertices());
				rightStates.addAll(rightAutomaton.vertices());
				
				for (SymbolClass.State state : leftAutomaton.vertices()) {
					rulesByState.put(state, rule);
					symbolClassesByState.put(state, rule.getLeftSymbolClass());
				}
				
				for (SymbolClass.State state : rightAutomaton.vertices()) {
					rulesByState.put(state, rule);
					symbolClassesByState.put(state, rule.getRightSymbolClass());
				}
			}
			
			for (SymbolClass symbolClass : Sets.newHashSet(automaton.edgeLabels())) {
				if (symbolClass == null) {
					continue;
				}
				
				if (symbolClass.toString().equals("\"=\"")) {
					System.out.print("");
				}
				
				if (!SymbolClasses.isAtomicAutomaton(symbolClass)) {
					modified |= rules.add(new Rule(concat(symbolClass), symbolClass));
				}
			}
		} while (modified);

		//System.out.println(wordCharacterRule.rightSide().automaton());
		//System.out.println(ifRule);
		//System.out.println(thenRule);
		
		ParseState initialCore = new ParseState(
				ImmutableSet.copyOf(grammar.getStartRule().getRightAutomaton().getStartVertices()),
				ImmutableSet.<SymbolClass.State>of()
			);
		System.out.println("Initial core:");
		print(initialCore);
		
		ParseState initial = closure(initialCore);
		System.out.println("Initial closure:");
		print(initial);
		
		parseAutomaton = GraphAutomaton.create();
		
		Deque<ParseState> unprocessedParseStates = Lists.newLinkedList();
		unprocessedParseStates.addLast(initial);
		
		parseAutomaton.addVertex(initial);
		parseAutomaton.addStartVertex(initial);
		
		while (!unprocessedParseStates.isEmpty()) {
			ParseState parseState = unprocessedParseStates.removeFirst();
			
			parseAutomaton.addVertex(parseState);
			
			Set<SymbolClass> outboundSymbolClasses = Sets.newHashSet();
			
			for (SymbolClass.State state : parseState.downStates()) {
				if (rightStates.contains(state)) {
					outboundSymbolClasses.addAll(automaton.outboundEdgeLabels(state));
				}
			}
			
			for (SymbolClass.State state : parseState.upStates()) {
				if (leftStates.contains(state)) {
					outboundSymbolClasses.addAll(automaton.outboundEdgeLabels(state));
				}
			}
			
			outboundSymbolClasses.remove(null);
			
			for (SymbolClass outboundSymbolClass : outboundSymbolClasses) {
				ParseState nextParseState = nextParseState(parseState, outboundSymbolClass);
				
				if (parseAutomaton.addVertex(nextParseState)) {
					unprocessedParseStates.addLast(nextParseState);
				}
				
				parseAutomaton.addDirectedEdge(parseState, nextParseState, outboundSymbolClass);
			}
		}
		
		//print(initial);
		
		for (ParseState state : parseAutomaton.vertices()) {
			
			if (parseAutomaton.getStartVertices().contains(state)) {
				System.out.println("START STATE:");
			}
			
			print(state);
			System.out.println("Outbound edges:");
			for (SymbolClass sc : parseAutomaton.outboundEdgeLabels(state)) {
				System.out.println("  " + sc);
			}
			
			LookAhead lookAhead = computeLookAhead(state);
			System.out.println("Look-ahead automaton: " + lookAhead.automaton);
			System.out.println("Look-ahead actions:");
			for (Map.Entry<List<SymbolClass>, Collection<Action>> entry : lookAhead.actionsByLookAheadString.asMap().entrySet()) {
				System.out.println("  " + entry);
			}
			System.out.println();
			System.out.println();
		}
		
		ClassWriter writer = new ClassWriter(grammar, parseAutomaton, Sets.newHashSet(rules));
		writer.writeParserFile();
	}

	private void computeNullableRules() {
		boolean modified;
		
		do {
			modified = false;
			
			
		} while (modified);
	}

	private void print(ParseState parseState) {
		Set<Rule> rules = Sets.newHashSet();
		
		for (SymbolClass.State downState : parseState.downStates()) {
			rules.add(rule(downState));
		}
		
		for (SymbolClass.State upState : parseState.upStates()) {
			rules.add(rule(upState));
		}
		
		System.out.println("Parse state:");
		
		System.out.println("  Down states:");
		for (SymbolClass.State downState : parseState.downStates()) {
			if (rightStates.contains(downState)) {
				System.out.println("    " + downState);
			}
		}
		
		//System.out.println("  Up states:");
		//for (SymbolClass.State upState : parseState.upStates()) {
		//	System.out.println("    " + upState);
		//}
		
		//for (Rule rule : rules) {
			//System.out.println("  " + rule.toString(parseState.downStates(), parseState.upStates()));
		//}
	}

	private ParseState closure(ParseState coreParseState) {
		Set<SymbolClass.State> downStates = Sets.newHashSet(coreParseState.downStates());
		Set<SymbolClass.State> upStates = Sets.newHashSet(coreParseState.upStates());
		
		boolean modified;
		do {
			modified = false;
			
			for (SymbolClass.State downState : Lists.newArrayList(downStates)) {
				SymbolClass symbolClass = symbolClassesByState.get(downState);
				if (symbolClass instanceof CharSequenceSymbolClass || symbolClass instanceof CharacterSymbolClass || symbolClass instanceof CharacterRangeSymbolClass) {
					continue;
				}
				
				modified |= downStates.addAll(automaton.successors(downState, null)); // Epsilon edges
				
				Collection<SymbolClass> downStateOutboundSymbolClasses = automaton.outboundEdgeLabels(downState);
				for (SymbolClass.State startState : automaton.getStartVertices()) {
					Collection<SymbolClass> startStateOutboundSymbolClasses = automaton.outboundEdgeLabels(startState);
					if (
						!intersection(downStateOutboundSymbolClasses, startStateOutboundSymbolClasses).isEmpty()
						||
						automaton.getAcceptVertices().contains(startState)
						) {
						if (isRightState(downState)) {
							if (isLeftState(startState)) {
								modified |= downStates.add(startState);
								modified |= downStates.addAll(rule(startState).getRightAutomaton().getStartVertices());
							} else {
								modified |= upStates.add(startState);
								modified |= upStates.addAll(rule(startState).getLeftAutomaton().getStartVertices());
							}
						}
					}
				}
			}
			
			for (SymbolClass.State upState : Lists.newArrayList(upStates)) {
				modified |= upStates.addAll(automaton.successors(upState, null)); // Epsilon edges
				
				for (SymbolClass.State startState : automaton.getStartVertices()) {
					if (!intersection(automaton.outboundEdgeLabels(upState), automaton.outboundEdgeLabels(startState)).isEmpty()) {
						if (isLeftState(upState) && isRightState(startState)) {
							modified |= upStates.add(startState);
							modified |= upStates.addAll(rule(startState).getLeftAutomaton().getStartVertices());
						}
					}
				}
			}
		} while (modified);
		
		return new ParseState(
				ImmutableSet.copyOf(downStates),
				ImmutableSet.copyOf(upStates)
			);
	}

	private boolean isLeftState(SymbolClass.State state) {
		return leftStates.contains(state);
	}

	private boolean isRightState(SymbolClass.State state) {
		return rightStates.contains(state);
	}

	private ParseState nextParseState(ParseState oldParseState, SymbolClass symbolClass) {
		Set<SymbolClass.State> newDownStates = Sets.newHashSet();
		Set<SymbolClass.State> newUpStates = Sets.newHashSet();
		
		for (SymbolClass.State oldDownState : oldParseState.downStates()) {
			newDownStates.addAll(automaton.successors(oldDownState, symbolClass));
		}
		
		for (SymbolClass.State oldUpState : oldParseState.upStates()) {
			newUpStates.addAll(automaton.successors(oldUpState, symbolClass));
		}
		
		return closure(new ParseState(newDownStates, newUpStates));
	}

	static class LookAhead {
		
		private final Automaton<List<SymbolClass>, SymbolClass> automaton;
		private final Multimap<List<SymbolClass>, Action> actionsByLookAheadString;
		
		public LookAhead() {
			this.automaton = Automatons.create();
			this.actionsByLookAheadString = HashMultimap.create();
		}
		
		public LookAhead(Automaton<List<SymbolClass>, SymbolClass> automaton, Multimap<List<SymbolClass>, Action> actionsByPath) {
			this.automaton = automaton;
			this.actionsByLookAheadString = actionsByPath;
		}
		
		
	}

	/**
	 * Computes an automaton that consumes up-coming input symbols in order to
	 * determine what action must be taken.
	 * 
	 * For example, if the state is LR(0), the resulting automaton will have
	 * only one vertex (this one vertex being both the "start" and "accept"
	 * vertex).
	 * 
	 * If the state is LR(1), the resulting automaton will have one "start"
	 * vertex and one or more "accept" vertices (linked by the symbol classes to
	 * be consumed).
	 * 
	 * So on and so forth...
	 * 
	 * @param parseState
	 * @return
	 */
	private LookAhead computeLookAhead(ParseState parseState) {
		Automaton<List<SymbolClass>, SymbolClass> lookAheadAutomaton = Automatons.create();
		Multimap<List<SymbolClass>, Action> actionsByLookAheadString = HashMultimap.create();
		
		LookAhead lookAhead = new LookAhead();
		
		List<SymbolClass> rootLookAheadString = ImmutableList.of();
		lookAheadAutomaton.addVertex(rootLookAheadString);
		lookAheadAutomaton.addStartVertex(rootLookAheadString);
		
		Multimap<SymbolClass, Action> actionsByLookAheadSymbolClass = HashMultimap.create();
		
		/*
		 * Symbol classes that transition out of this state induce SHIFT actions
		 */
		for (SymbolClass symbolClass : parseAutomaton.outboundEdgeLabels(parseState)) {
			actionsByLookAheadSymbolClass.put(symbolClass, new Shift());
		}
		
		/*
		 * Symbol classes that may be consumed after reducing a right-hand-side and yielding its
		 * left-hand-side induce REDUCE actions.
		 */
		for (State state : parseState.downStates()) {
			if (isReduceableState(state)) {
				for (SymbolClass a : lalrLookAheadSymbolClasses(parseState, state)) {
					actionsByLookAheadSymbolClass.put(a, new Reduction(rule(state)));
				}
			}
		}
		
		Set<Action> uniqueActions = Sets.newHashSet(actionsByLookAheadSymbolClass.values());
		lookAhead.actionsByLookAheadString.putAll(rootLookAheadString, uniqueActions);
		
		if (uniqueActions.size() <= 1) {
			lookAheadAutomaton.addAcceptVertex(rootLookAheadString);
		} else {
			for (Map.Entry<SymbolClass, Collection<Action>> actionsBySymbolClass : actionsByLookAheadSymbolClass.asMap().entrySet()) {
				Collection<Action> actions = actionsBySymbolClass.getValue();
				
				if (actions.size() > 1) {
					SymbolClass conflictingSymbolClass = actionsBySymbolClass.getKey();
					Multimap<Action, List<ParseState>> sourcesByAction = HashMultimap.create();
					
					for (Action action : actionsBySymbolClass.getValue()) {
						if (action instanceof Shift) {
							sourcesByAction.put(action, ImmutableList.of(parseState));
						} else {
							// Reduction
							Reduction reduction = (Reduction) action;
							Rule rule = reduction.rule;
							for (ParseState predecessor : predecessors(parseState, rule.getRightSymbolClass().toAutomaton())) {
								List<ParseState> stack = ImmutableList.of(predecessor);
								Collection<List<ParseState>> followSources = followSources(stack, rule, conflictingSymbolClass);
								
								sourcesByAction.putAll(action, followSources);
							}
						}
					}
					
					ImmutableList<SymbolClass> newLookAheadString = ImmutableList.of(conflictingSymbolClass);
					resolveConflicts(parseState, lookAhead, newLookAheadString, conflictingSymbolClass, sourcesByAction, 2);
				}
			}
		}
		
		return lookAhead;
	}

	/**
	 * Returns {@code true} if an LR(0) parser may reduce in this state. 
	 * 
	 * @param state
	 * @return
	 */
	private boolean isReduceableState(SymbolClass.State state) {
		return automaton.getAcceptVertices().contains(state) && !automaton.getRejectVertices().contains(state);
	}

	private boolean isLR0(ParseState parseState) {
		Set<SymbolClass.State> right = Sets.newHashSet();
		
		for (SymbolClass.State s : parseState.downStates()) {
			if (rightStates.contains(s)) {
				right.add(s);
			}
		}
		
		if (right.size() <= 1) {
			return true;
		}
		
		for (SymbolClass.State s : right) {
			if (automaton.getAcceptVertices().contains(s)) {
				return false;
			}
		}
		
		return true;
	}

	private Collection<SymbolClass> lookAheadSymbols(ParseState parseState, SymbolClass.State finalState) {
		return null;
	}

	private Collection<? extends SymbolClass> la(ParseState parseState, SymbolClass.State finalState) {
		return null;
	}

	private void read() {
		
	}

	private void follow() {
		
	}

	private Collection<ParseState> predecessors(ParseState parseState, Automaton<? extends SymbolClass.State, ? extends SymbolClass> automaton) {
		Set<ParseState> predecessors = Sets.newHashSet();
		
		for (Path<? extends SymbolClass.State, ? extends SymbolClass> path : automaton.getPaths()) {
			predecessors.addAll(pathPredecessors(parseState, path));
		}
		
		return predecessors;
	}

	private Collection<ParseState> pathPredecessors(ParseState parseState, Path<? extends SymbolClass.State, ? extends SymbolClass> path) {
		Set<ParseState> predecessors = Sets.newHashSet();
		
		if (path.isEmpty()) {
			predecessors.add(parseState);
		} else {
			SymbolClass lastSymbolClass = path.getLastEdge().getLabel();
			
			for (ParseState predecessor : parseAutomaton.predecessors(parseState, lastSymbolClass)) {
				predecessors.addAll(pathPredecessors(predecessor, path.to(path.size() - 1)));
			}
		}
		
		return predecessors;
	}

	private Collection<List<ParseState>> followSources(List<ParseState> stack, Rule rule, SymbolClass conflictingSymbolClass) {
		SymbolClass leftHandSymbolClass = Iterables.getOnlyElement(rule.getLeftAutomaton().edgeLabels());
		return followSources(stack, rule, leftHandSymbolClass, conflictingSymbolClass, Sets.<Pair<ParseState, Rule>>newHashSet());
	}

	/**
	 * 
	 * @param stack
	 * @param leftHandSymbolClass
	 * @param conflictingSymbolClass
	 * @param visited
	 * @return
	 */
	private Collection<List<ParseState>> followSources(
			List<ParseState> stack,
			Rule rule,
			SymbolClass leftHandSymbolClass,
			SymbolClass conflictingSymbolClass,
			Collection<Pair<ParseState, Rule>> visited)
	{
		Set<List<ParseState>> stacks = Sets.newHashSet();
		
		ParseState topState = stack.get(stack.size() - 1);
		
		if (stack.size() == 1 && !visited.add(Pair.create(topState, rule))) {
			return ImmutableSet.of();
		}
		
		ParseState nextState = Iterables.getOnlyElement(parseAutomaton.successors(topState, leftHandSymbolClass));
		
		if (dr(topState, leftHandSymbolClass).contains(conflictingSymbolClass)) {
			List<ParseState> newStack = ImmutableList.<ParseState>builder()
				.addAll(stack)
				.add(nextState)
				.build();
			
			stacks.add(newStack);
		}
		
		for (SymbolClass outboundSymbolClass : parseAutomaton.outboundEdgeLabels(nextState)) {
			if (nullable(outboundSymbolClass)) {
				List<ParseState> newStack = ImmutableList.<ParseState>builder()
					.addAll(stack)
					.add(nextState)
					.build();
				
				stacks.addAll(followSources(newStack, rule, outboundSymbolClass, conflictingSymbolClass, visited));
			}
		}
		
		for (SymbolClass.State state : topState.downStates()) {
			Automaton<? extends SymbolClass.State, ? extends SymbolClass> automaton = rule(state).getRightAutomaton();
			
			if (((Automaton) automaton).outboundEdges(state, leftHandSymbolClass).isEmpty()) {
				continue;
			}
			
			Automaton<? extends SymbolClass.State, ? extends SymbolClass> la = rule(state).getLeftAutomaton();
			
			SymbolClass.State ss = Iterables.getOnlyElement(la.getStartVertices());
			
			Collection<? extends SymbolClass> sss = ((Automaton) la).outboundEdgeLabels(ss);
			if (sss.isEmpty()) {
				continue;
			}
			
			SymbolClass lhs = Iterables.getOnlyElement(sss);
			
			for (Path<? extends SymbolClass.State, ? extends SymbolClass> path : Automatons.pathsTo(automaton, state)) {
				if ((path.size() + 1) < stack.size()) {
					List<ParseState> newStack = stack.subList(0, stack.size() - path.size());
					stacks.addAll(followSources(newStack, rule, lhs, conflictingSymbolClass, visited));
				} else {
					Path<? extends SymbolClass.State, ? extends SymbolClass> head = path.to((path.size() + 1) - stack.size());
					for (ParseState predecessor : predecessors(stack.get(0), head)) {
						List<ParseState> newStack = ImmutableList.of(predecessor);
						stacks.addAll(followSources(newStack, rule, lhs, conflictingSymbolClass, visited));
					}
				}
			}
		}
		
		return stacks;
	}

	private boolean nullable(SymbolClass symbolClass) {
		return false;
	}

	/**
	 * Returns the symbol classes that may be read after reading a symbol of
	 * the given symbolClass from the given state.
	 * 
	 * @param state
	 * @param symbolClass
	 * @return
	 */
	private Collection<SymbolClass> dr(ParseState state, SymbolClass symbolClass) {
		Collection<SymbolClass> dr = Sets.newHashSet();
		
		for (ParseState successor : parseAutomaton.successors(state, symbolClass)) {
			dr.addAll(parseAutomaton.outboundEdgeLabels(successor));
		}
		
		return dr;
	}

	private static interface Action {
		
	}

	private static class Shift implements Action {
		
		private final transient int hashCode = HashCodes.classSpecificHashCode(Shift.class);

		@Override
		public String toString() {
			return "SHIFT";
		}
		
		@Override
		public int hashCode() {
			return hashCode;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			
			if (obj == null) {
				return false;
			}
			
			return getClass() == obj.getClass();
		}

	}

	private static class Reduction implements Action {
		
		private final Rule rule;
		private final transient int hashCode;

		public Reduction(Rule rule) {
			this.rule = rule;
			this.hashCode = HashCodes.classSpecificHashCode(Shift.class, rule);
		}

		@Override
		public String toString() {
			return "REDUCE{" + rule + "}";
		}
		
		@Override
		public int hashCode() {
			return hashCode;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			
			if (obj == null) {
				return false;
			}
			
			if (getClass() != obj.getClass()) {
				return false;
			}
			
			Reduction other = (Reduction) obj;
			if (rule == null) {
				if (other.rule != null)
					return false;
			} else if (!rule.equals(other.rule))
				return false;
			return true;
		}
		
	}

	/**
	 * Resolves conflicts in an inconsistent state by increasing the length of the look-ahead string.
	 * 
	 * @param parseState
	 * @param lookAhead
	 * @param lookAheadString
	 * @param conflictingSymbolClass
	 * @param sources
	 * @param lookAheadSize
	 */
	private void resolveConflicts(
			ParseState parseState,
			LookAhead lookAhead,
			List<SymbolClass> lookAheadString,
			SymbolClass conflictingSymbolClass,
			Multimap<Action, List<ParseState>> sources,
			int lookAheadSize
	) {
		if (lookAheadSize > MAX_LOOKAHEAD_SIZE) {
			return;
		}
		
		List<SymbolClass> newLookAheadString = ImmutableList.<SymbolClass>builder()
			.addAll(lookAheadString)
			.add(conflictingSymbolClass)
			.build();
		
		lookAhead.automaton.addVertex(newLookAheadString);
		
		Multimap<SymbolClass, Action> actionsBySymbolClass = HashMultimap.create();
		
		for (Map.Entry<Action, List<ParseState>> entry : sources.entries()) {
			List<ParseState> stack = entry.getValue();
			for (SymbolClass symbolClass : nextLookAhead(stack, conflictingSymbolClass)) {
				actionsBySymbolClass.put(symbolClass, entry.getKey());
			}
		}
		
		Set<Action> uniqueActions = Sets.newHashSet(actionsBySymbolClass.values());
		lookAhead.actionsByLookAheadString.putAll(newLookAheadString, uniqueActions);
		lookAhead.automaton.addVertex(newLookAheadString);
		
		if (uniqueActions.isEmpty()) {
			
		} else if (uniqueActions.size() == 1) {
			
		} else {
			for (Map.Entry<SymbolClass, Collection<Action>> entry : actionsBySymbolClass.asMap().entrySet()) {
				Collection<Action> actions = entry.getValue();
				
				if (actions.size() > 1) {
					SymbolClass newConflictingSymbolClass = entry.getKey();
					Multimap<Action, List<ParseState>> newSources = HashMultimap.create();
					
					for (Action action : actions) {
						for (List<ParseState> stack : sources.get(action)) {
							newSources.putAll(action, followSources(stack, null /* rule */, newConflictingSymbolClass));
						}
					}
					
					resolveConflicts(parseState, lookAhead, newLookAheadString, newConflictingSymbolClass, newSources, lookAheadSize + 1);
				}
			}
		}
	}

	private Collection<SymbolClass> nextLookAhead(List<ParseState> stack, SymbolClass symbolClass) {
		ParseState top = stack.get(stack.size() - 1);
		ParseState successor = Iterables.getOnlyElement(parseAutomaton.successors(top, symbolClass));
		
		return null;
	}

	private Collection<SymbolClass> lookAhead(ParseState parseState, Rule rule) {
		return null;
	}

	private Rule rule(SymbolClass.State state) {
		return rulesByState.get(state);
	}

	private <E> Set<E> intersection(Iterable<? extends E> a, Iterable<? extends E> b) {
		Set<E> aa = Sets.newHashSet(a);
		aa.remove(null);
		
		Set<E> bb = Sets.newHashSet(b);
		bb.remove(null);
		
		return Sets.intersection(aa, bb);
	}

	private Collection<SymbolClass> trans(ParseState parseState) {
		Set<? super ParseState> visitedParseStates = Sets.newHashSet();
		return trans(parseState, visitedParseStates);
	}

	private Collection<SymbolClass> trans(ParseState parseState, Set<? super ParseState> visitedParseStates) {
		if (!visitedParseStates.add(parseState)) {
			return ImmutableSet.of();
		}
		
		Set<SymbolClass> lookAheadSymbolClasses = Sets.newHashSet();
		
		for (SymbolClass.State state : parseState.downStates()) {
			for (SymbolClass lookAheadSymbolClass : rule(state).getRightAutomaton().outboundEdgeLabels(state)) {
				lookAheadSymbolClasses.add(lookAheadSymbolClass);
				for (ParseState successorParseState : parseAutomaton.successors(parseState, lookAheadSymbolClass)) {
					lookAheadSymbolClasses.addAll(trans(successorParseState, visitedParseStates));
				}
			}
		}
		
		Iterables.removeIf(lookAheadSymbolClasses, Predicates.isNull());
		
		return lookAheadSymbolClasses;
	}

	private Collection<SymbolClass> lalrLookAheadSymbolClasses(ParseState parseState, SymbolClass.State state) {
		Set<? super Pair<ParseState, SymbolClass.State>> visitedArguments = Sets.newHashSet();
		return lalrLookAheadSymbolClasses(parseState, state, visitedArguments);
	}

	private Collection<SymbolClass> lalrLookAheadSymbolClasses(
			ParseState parseState,
			SymbolClass.State state,
			Set<? super Pair<ParseState, SymbolClass.State>> visitedArguments
	) {
		if (!visitedArguments.add(Pair.create(parseState, state))) {
			return ImmutableSet.of();
		}
		
		if (leftStates.contains(state)) {
			return ImmutableSet.of();
		}
		
		Automaton<State, SymbolClass> lhs = rule(state).getLeftAutomaton();
		State lhsStart = Iterables.getOnlyElement(lhs.getStartVertices());
		Collection<SymbolClass> lhsStartSymbols = lhs.outboundEdgeLabels(lhsStart);
		if (lhsStartSymbols.size() != 1) {
			return ImmutableSet.of();
		}
		SymbolClass lhsStartSymbol = Iterables.getOnlyElement(lhsStartSymbols);
		
		Set<SymbolClass> lookAheadSymbolClasses = Sets.newHashSet();
		
		Automaton<SymbolClass.State, SymbolClass> newAutomaton = Automatons.create(rule(state).getRightAutomaton());
		newAutomaton.getAcceptVertices().clear();
		newAutomaton.addAcceptVertex(state);
		
		for (ParseState predecessor : predecessors(parseState, newAutomaton)) {
			lookAheadSymbolClasses.addAll(trans(predecessor));
			for (SymbolClass.State predecessorState : predecessor.downStates()) {
				Automaton<SymbolClass.State, SymbolClass> predecessorStateAutomaton = rule(predecessorState).getRightAutomaton();
				
				for (Path<SymbolClass.State, SymbolClass> path : Automatons.pathsFrom(predecessorStateAutomaton, predecessorState)) {
					if (path.isEmpty()) {
						continue;
					}
					
					if (lhsStartSymbol.equals(path.getFirstEdgeLabel()) && !nullable(path.from(1))) {
						lookAheadSymbolClasses.addAll(lalrLookAheadSymbolClasses(predecessor, predecessorState, visitedArguments));
					}
				}
			}
		}
		
		return lookAheadSymbolClasses;
	}

	private boolean nullable(Path<SymbolClass.State, SymbolClass> path) {
		for (SymbolClass symbolClass : path.edgeLabels()) {
			if (!nullable(symbolClass)) {
				return false;
			}
		}
		
		return true;
	}

}
